package com.adee.nowcoder.exercise;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class T001_LCS {
    public static void main(String[] args) {
        String s1 = "asdf123459jkeuv73hfkud";
        String s2 = "09fdu3hfy62g6cgw3y4gfbuuqw716grjcuwgqkft52br";
        System.out.println(LCS(s1, s2));

    }

    public static String LCS (String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();

        if (arr1.length == 0 || arr2.length == 0) {
            return "-1";
        }

        int[][] mt = new int[arr1.length + 1][arr2.length + 1];  // 左边和上边多出两条边，都填充0

        mt[0][0] = arr1[0] == arr2[0] ? 1 : 0;

        // 填充左边和上边，两条边
        for (int i = 0; i < arr1.length; ++i) {
            mt[i][0] = 0;
        }
        for (int j = 0; j < arr2.length; ++j) {
            mt[0][j] = 0;
        }

        // 递推
        for (int i = 1; i <= arr1.length; ++i) {
            for (int j = 1; j <= arr2.length; ++j) {
                if (arr1[i-1] == arr2[j-1]) {
                    mt[i][j] = mt[i-1][j-1] + 1;
                } else {
                    mt[i][j] = Math.max(mt[i-1][j], mt[i][j-1]);
                }
            }
        }

        // 递推算出来LCS个数后，反向找序列
        StringBuilder sb = new StringBuilder();
        for (int i = arr1.length, j = arr2.length; i > 0 && j > 0; ) {
            if (arr1[i-1] == arr2[j-1]) {
                sb.append(arr1[i-1]);
                --i;
                --j;
            } else {
                if (mt[i-1][j] > mt[i][j-1]) {
                    --i;
                } else {
                    --j;
                }
            }
        }

        String s = sb.reverse().toString();
        if (s == null || s.length() == 0) {
            return "-1";
        }

        return s;
    }
}
